import java.util.Arrays;

public class PriorityQueue {
    int[] elem;
    int usedSize;
    public PriorityQueue(int[] array) {
        elem = Arrays.copyOf(array,array.length);
        usedSize = array.length;
    }
    public void creatHeap(){
        //从最后一个子树的父结点开始
        for (int parent = (usedSize-1-1)/2;parent >= 0;parent--) {
            shiftDown(parent,usedSize);
        }
    }
    public void shiftDown(int parent,int stop){
        int child = parent*2+1;//左孩子结点
        //如果左孩子结点存在
        while (child<stop){
            /*如果右孩子结点存在，且左孩子结点大于右孩子结点的值*/
            /*经过下面的if语句判断后，要保证此时child下标的值是两个子节点中最大值*/
            if ((child+1 < stop) && (elem[child] < elem[child+1])){
                child++;
            }
            /*然后开始比较子结点中的最大值与父结点的大小
            * 如果父结点较大，那么子树中没有比父结点大的了，就进入下一次循环判断*/
            if (elem[child] > elem[parent]){
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                /*这里是将父结点向下移，判断这个最大的子节点为根节点的树中是否有比父结点更大的值
                * 即：确实是从最后一个结点所在的子树开始往上找的，不能保证已经满足大根堆的子树中，除了
                * 根节点外，其他节点都比新来的父结点小*/
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        PriorityQueue priorityQueue = new PriorityQueue(array);
        priorityQueue.creatHeap();
        System.out.println("******************");
    }
}
